题目

给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4

解答

思路

同上，中序遍历可以获得二叉搜索树的递增序列，但这里要求第 k 大的节点值，如果不求总节点的个数，在递增序列中没法找第 K 大。

所以需要对中序遍历进行修改，改成 右根左 的遍历顺序，这样得到的遍历结果就是递减序列。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int res, k;
    void dfs(TreeNode* root){
        if(root == NULL) return ;
        dfs(root->right); // 右
        if(--k == 0){
            res = root->val; // 根
            return ; // 获得结果提前跳出
        };
        dfs(root->left); // 左
    }
    int kthLargest(TreeNode* root, int k) {
        this->k = k;
        dfs(root);
        return res;
    }
};

复杂度

  • 时间复杂度 O(N) ：访问树的所有节点。
  • 空间复杂度 O(N) ：系统栈空间。